package demo;

import java.util.Arrays;

public class PriorityQueue {
    private int usedsize ;   //二叉树中元素的个数
    public int [] elem;
    public PriorityQueue(){
        this.elem = new int[10];
    }
    //创建大根堆
    public void BigPriorityQueue(){
        //首先找到最后一棵子树
        //在堆中，最后一棵子树的节点坐标为？不需要区分左节点与右节点的区别
        for (int parent = this.usedsize-1-1; parent >=0 ; parent--) {
            //在找到每一刻子树的根节点后，开始进行比较替换
            Sift(parent,this.usedsize);
        }
    }
   public void SiftDown( int parent, int usedsize ){
        //开始进行比较
        //对于每一棵子树
        //比较左子树与右子树
       int child = parent*2 +1; //左节点
       //对于一棵树要比较其从上到下的根节点与其左右节点
       while (child<usedsize) {
           //这是判断存在右节点，然后左右节点大于根节点的情况，两种可能的情况都有替换值的代码，能否抽象一下？
           //先找到左右节点中较大的值
               if (child + 1 < usedsize && elem[child]<elem[child+1]) {
                   //此时找到左右节点的最大值
                  child = child+1;
               }
               //右节点存在与右节点不存在能否抽象成一段代码？
              //确保最大值为左节点即可。我们判断右节点是否存在，是为了找出其最大值
              if(elem[child] >elem[parent]){
                  //交换两者的值
                  int tmp = elem[child];
                  elem[child] = elem[parent];
                  elem[parent] = tmp;
                  //在交换完毕之后，将此刻的孩子节点变为根节点
                  //另一个孩子节点不需要再进行比较，因为其没有变动过
                  parent = child;
                  child = 2* parent+1;
           }else {
                  break;
              }
       }

       //如果是此种比较方法，如何再比较下一个堆呢？
   }
   public void push(int val){
        //开始加入新的元素到堆中
      if(isFull()){
          this.elem = Arrays.copyOf(this.elem,this.elem.length*2);
      }
       this.elem[usedsize] = val;
       SiftUp(usedsize);
        usedsize++;
   }



  public  void SiftUp(int child) {
      int parent = (child - 1) / 2;
      while (parent >= 0) {
          if (elem[child] > elem[parent]) {
              int tmp = elem[child];
              elem[child] = elem[parent];
              elem[parent] = tmp;
              child = parent;
              parent = (child - 1) / 2;
          } else {
              break;
          }

      }
  }
   private boolean isFull(){
       //判断是否为空
   return    this.elem.length == usedsize;
      }
      //删除堆中的元素
      public int  pop(int val){
         int ret = elem[0];
         int tmp = elem[0];
         elem[0] = elem[usedsize-1];
         elem[usedsize-1] =elem[0];
         SiftDown(0,usedsize-1);
         usedsize--;
         return ret;
      }
  public int peek(){


        return elem[0];
  }


  }

